package twice.class_digui;

import sun.text.resources.cldr.ti.FormatData_ti;

public class Class22_NQueens {
    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process1(0, record, n);
    }

    public static int process1(int i,int[] record,int n){
        if(i == n){
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if(isVailed(record,i,j)){
                record[i] = j;
                res += process1(i + 1,record,n);
            }
        }
        return res;
    }
    public static boolean isVailed(int[] record,int i,int j){
        for (int k = 0; k < i; k++) {
            if(j == record[k] || Math.abs(record[k] - j) ==Math.abs(i - k)){
                return false;
            }
        }
        return true;
    }

    public static int num2(int n){
        if(n < 1 || n > 32){
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit,0,0,0);
    }
    // 7皇后问题
    // limit : 0....0 1 1 1 1 1 1 1
    // 之前皇后的列影响：colLim
    // 之前皇后的左下对角线影响：leftDiaLim
    // 之前皇后的右下对角线影响：rightDiaLim
    public static int process2(int limit,int colLim, int leftDiaLim, int rightDiaLim){
        if(colLim == limit){
            return 1;
        }
        //post 中1的位置是可以尝试的位置
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;
        int res = 0;
        while(pos != 0){
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(limit,colLim | mostRightOne ,
                    (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;

    }

    public static void main(String[] args) {
        int n = 15;

        long start;
        long end;

        start = System.currentTimeMillis();
        System.out.println(num2(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

    }
}
